The present invention relates to a method for adaptively tessellating an arbitrary shape, defined by a closed curve, into a set of mosaic tiles.
Mosaic tiles are relatively well known. In essence, an image is constructed using fragments of tiles or glass embedded in a cement mixture. The overall resolution is less than that which might be achieved by, say, painting the image. However, the fragmented appearance of the tiles in itself provides visual interest to an observer.
The effect provided by mosaic tiles has been imitated for application to digital images stored on a computer or the like. Typically, a series of control points is generated across a given image, and then joined to form tile edges. Each tile is then provided with a base colour associated with its position on the image. For example, the colour of a single pixel corresponding to a central point in the tile may be selected as the colour for the entire tile. Alternatively, some form of colour averaging may be used to produce a single colour.
Some software packages allow a user to manually define control lines corresponding to areas of interest, using a mouse or other input device. The control points and mosaic tiles are then generated on the basis of these control lines. However, this is a relatively labour intensive approach.
There is a desire to provide a visually interesting mosaic effect which reduces the randomness of tile placement whilst allowing areas defined by closed curves to be clearly delineated from other areas of an image.
Accordingly, the present invention provides a method of producing a mosaic effect in an image to be printed or displayed, the method including the steps of:
(a) providing a first closed curve;
(b) generating regularly spaced boundary points along the first closed curve;
(c) filling an area adjacent to the closed curve with generally regularly spaced fill points;
(d) triangulating the fill points and the boundary points to generate a series of polygons, thereby to generate a mosaic pattern in the area adjacent to the first closed curve; and
(e) rendering the polygons for printing, storage or display.
Preferably, the area adjacent to the first closed curve is within the first closed curve. It is further preferred that the method include the step of providing one or more secondary closed curves disposed within the first closed curve. In this case, the area adjacent the first closed curve is bounded internally by the secondary closed curve. The method then further includes a step (ii), prior to step (d), of generating regularly spaced secondary boundary points along each of the secondary closed curves, the secondary boundary points being triangulated with the boundary points and the fill points during step (d).
Preferably, step (d) includes the sub-step of converting at least some of the triangulated polygons into non-triangular polygons.
It is particularly desirable that step (c) includes the sub-steps of:
(ii) deriving from each of the boundary points a wavefront extending into an area adjacent the closed curve, the wavefront comprising a series of fill points, each fill point being a predetermined distance from its associated boundary point;
(iv) where multiple fill points fall within a predetermined distance of each other, combining the multiple fill points to generate a new fill point;
(v) using fill points generated by the wavefront and sub-step (iv) as new starting points for a new wavefront; and
(vi) iteratively repeating sub-steps (ii) to (v) until the area adjacent the closed curve is filled with approximately equally spaced fill points.
Other preferences and aspects of the invention will be apparent from the associated detailed description and the numbered paragraphs which follow.